package leetcode

import kotlinetc.createNodeList
import kotlinetc.println
import kotlinetc.toList

/**
Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4
Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5
 */
fun main(args: Array<String>) {

//    sortList(createNodeList("-1->5->3->4->0")).toList().println()


//    mergeList(createNodeList(" 1->2->4 "), createNodeList(" 1->3->4 ")).toList().println()


    sortList(createNodeList("-1->5->3->4->0")).toList().println()

}

fun sortList(head: ListNode?): ListNode? {

    if (head?.next == null)  //这句很重要，当分割到只有一个元素的时候不再分割
        return head

    //N log(N)复杂度就是归并排序
    //用两个指针分割 list
    var fast = head
    var slow = head
    var prev: ListNode? = null

    //until fast pointer move to the end of the list
    while (fast != null && fast.next != null) {
        prev = slow
        slow = slow?.next
        fast = fast.next?.next
    }

    //cut into halves
    prev?.next = null

    val list1 = sortList(head)

    val list2 = sortList(slow)

    return mergeList(list1, list2)
}

fun mergeList(l1: ListNode?, l2: ListNode?): ListNode? {

    var p: ListNode? = ListNode(0, null)

    var p1 = l1
    var p2 = l2

    val head = p

    while (p1 != null && p2 != null) {

        if (p1.`val` < p2.`val`) {
            p?.next = p1
            p1 = p1.next
        } else {
            p?.next = p2
            p2 = p2.next
        }

        p = p?.next
    }

    //有一个列表还没有访问完，直接拼在最后
    if (p1 != null)
        p?.next = p1

    if (p2 != null)
        p?.next = p2

    return head?.next
}